public class Solution1823 {

    class Node{
        int val;
        Node last;
        Node next;

        Node(int val){
            this.val = val;
        }
    }

    private Node buildAndGetHead(int n){
        Node head = new Node(1);
        Node tmpNode = head;
        for(int i = 2; i <= n; i++){
            Node newNode = new Node(i);
            tmpNode.next = newNode;
            newNode.last = tmpNode;
            tmpNode = newNode;
        }
        head.last = tmpNode;
        tmpNode.next = head;
        return head;
    }

    private Node getForwardNode(Node node, int step){
        Node forwardNode = node;
        for(int i = 0; i < step; i++){
            forwardNode = forwardNode.next;
        }
        return forwardNode;
    }

    private void removeNode(Node node){
        Node lastNode = node.last, nextNode = node.next;
        lastNode.next = nextNode;
        nextNode.last = lastNode;
    }

    public int findTheWinner(int n, int k) {
        Node startNode = buildAndGetHead(n);
        for(int i = 0; i < n - 1; i++){
            Node loserNode = getForwardNode(startNode, k - 1);
            startNode = loserNode.next;
            removeNode(loserNode);
        }
        return startNode.val;
    }
}
